package graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 腐烂的橘子
 */
public class Solution_994 {

    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};

    /**
     * 把所有烂橘子一次性塞进队列，然后逐层向外 BFS，层数就是所需分钟数。
     */
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int fresh = 0;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    fresh++;
                } else if (grid[i][j] == 2) {
                    queue.add(new int[]{i, j});
                }
            }
        }
        if (fresh == 0) return 0;
        int minute = 0;
        while (!queue.isEmpty() && fresh > 0) {
            minute++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int x0 = cur[0], y0 = cur[1];
                for (int d = 0; d < 4; d++) {
                    int x = x0 + dx[d];
                    int y = y0 + dy[d];
                    if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] != 1)
                        continue;
                    grid[x][y] = 2;
                    fresh--;
                    queue.offer(new int[]{x, y});
                }
            }
        }
        return fresh > 0 ? -1 : minute;
    }
}
